#include <iostream>
#include <ctime>
#include <vector>
#include <queue>
#include <string>
#include <memory>
#include <functional>
#include <algorithm>
#include <thread>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>

struct PCB {
    std::string pid_name;   // 进程标识
    char state;             // 进程当前状态
    int priority;           // 进程优先级
    int neededTime;         // 进程运行需要的时间
    int arrivalTime;        // 进程到达的时间
    int usedTime;           // 累计运行时间
    int totalWaitTime;      // 进程等待CPU时间的总和
    bool isUpdate;          // 用于记录当前进程的等待时间是否更新

    PCB(const std::string& pname, char pstate, 
        int ppriority, int pneedTime, int parrival, int utime,int ptotaltime = 0)
        : pid_name(pname),
          state(pstate),
          priority(ppriority),
          neededTime(pneedTime),
          arrivalTime(parrival),
          usedTime(utime),
          totalWaitTime(ptotaltime),
          isUpdate(false)
    {}
};

struct Rqueue {
    int number;             // 队列的标号
    int priority;           // 队列优先级
    int timeSlice;          // 队列时间片长度
    std::vector<PCB*> list;      // 存放进程的队列

    using ptr = std::shared_ptr<Rqueue>;

    Rqueue(int ptime, int ts, int num)
        : priority(ptime),
          timeSlice(ts),
          number(num)
    {}
};

#define QUEUE_NUM 5
#define PROCESS_NUM 20
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
double totalWaitTime = 0;
sem_t sem_scheduler;
std::vector<Rqueue> rqueue;
// Rqueue rqueue[QUEUE_NUM];
int Time = 0; // 全局时间，用于记录进程执行时消耗的时间

// 对sem进行P操作，占用一个信号量
void P_sem(sem_t& sem) {
    sem_wait(&sem);
}

// 释放一个信号量，信号量加加
void V_sem(sem_t& sem) {
    sem_post(&sem);
}


void init() {
    // 初始化队列
    for (int i = 0; i < QUEUE_NUM; i++) {
        rqueue.push_back(Rqueue(i + 1, 10 * (1 << i), i + 1));
    }
    // 初始化信号量
    sem_init(&sem_scheduler, 0, 0);
}

void* generator(void* args) {
    for (int i = 0; i < PROCESS_NUM; i++) {

        pthread_mutex_lock(&mutex);

        int needTime = rand() % 199 + 2;
        PCB* pcb = new PCB("P" + std::to_string(i), 'w', 1, needTime, Time, 0);
        rqueue[0].list.push_back(pcb);
        printf("Generator: Process %s is generated, neededTime = %d, arrivalTime = %d\n",
            pcb->pid_name.c_str(), pcb->neededTime, pcb->arrivalTime);
        int sleep_time = rand() % 100 + 1;
        printf("Generator: Sleep for %d ms after generatint next new process\n", sleep_time);

        pthread_mutex_unlock(&mutex);    
        // 当scheduler执行结束之后，才会运行下去
        V_sem(sem_scheduler);

        std::this_thread::sleep_for(std::chrono::microseconds(sleep_time * 1000));
        // usleep(sleep_time * 1000);


    }    
    return nullptr;    
}

void updateWaitTime(int sleepTime) {
    for (int i = 0; i < QUEUE_NUM; i++) {
        for (auto& it : rqueue[i].list) 
            it->totalWaitTime += sleepTime;
    }
}

void executor(int index) {
    pthread_mutex_lock(&mutex);
    // 从队列中拿出任务
    PCB* task = rqueue[index].list.front();
    auto it = rqueue[index].list.begin();
    rqueue[index].list.erase(it);

    int timeSlice = rqueue[index].timeSlice;
    int sleepTime = (timeSlice + task->usedTime > task->neededTime) ? task->neededTime - task->usedTime : timeSlice;

    std::this_thread::sleep_for(std::chrono::microseconds(sleepTime * 1000));
    // usleep(sleepTime * 1000);
    Time += sleepTime;
    updateWaitTime(sleepTime);

    task->usedTime += sleepTime;

    pthread_mutex_unlock(&mutex);
    printf("Executor: Process %s in queue %d consumes %d ms\n",
        task->pid_name.c_str(), index + 1, sleepTime);   
}

void showQueue() {
    for (auto& rq : rqueue) {
        std::cout << "Queue " << rq.number << ":";
        for (auto it : rq.list) {
            std::cout << it->pid_name << " ";
        }
        std::cout << std::endl;
    }
}

bool queueIsEmpty() {
    for (auto& rq : rqueue) {
        if (!rq.list.empty())
            return false;
    }
    return true;
}

void scheduler() {
    int processNum = 0;
    
    P_sem(sem_scheduler);

    // processNum++;
    while (true) {

        for (int i = 0; i < QUEUE_NUM; i++) {
            while (!rqueue[i].list.empty()) {
                if (sem_trywait(&sem_scheduler) == 0) {
                    // 当前信号量被设置，退出循环，从第一个队列重新开始
                    // 信号量被设置，说明新的进程来临
                    // 最后一个进程进来的时候processNum变为19，并且不会在进入，将会形成死循环
                    // 需要在下文中进行特别的判定
                    processNum++;
                    break;
                }
                // 取出队列
                pthread_mutex_lock(&mutex);
                PCB* task = rqueue[i].list.front();
                pthread_mutex_unlock(&mutex);

                // 执行
                executor(i);

                pthread_mutex_lock(&mutex);
                // 判断当前进程如何处理
                if (task->pid_name == "P19") 
                    processNum++;
                
                if (task->usedTime < task->neededTime) {
                    // 当前进程未执行结束
                    if (task->priority < QUEUE_NUM) {
                        task->priority++;
                        rqueue[i+ 1].list.push_back(task);
                        printf("Scheduler: Process %s is moved to queue %d, priority = %d\n",
                               task->pid_name.c_str(), i + 2, task->priority);
                    } else {
                        // 如果队列已经无法下移，为了确保系统正确运行，则直接丢弃/释放进程。
                        printf("Scheduler: Process %s is running overtime, total waiting time = %d, aborted.\n",
                               task->pid_name.c_str(), task->totalWaitTime);
                        totalWaitTime += task->totalWaitTime;
                        delete task;
                    } 
                } else {
                    // 进程执行完毕，释放进程
                    printf("Scheduler: Process %s finished, total waiting time = %d\n",
                        task->pid_name.c_str(), task->totalWaitTime);    
                    totalWaitTime += task->totalWaitTime;
                    delete task;
                }
                showQueue();
                pthread_mutex_unlock(&mutex);
            }
        }
        
        // 只有当进程都生产完并且当前队列为空时才退出
        if (processNum > PROCESS_NUM && queueIsEmpty())   
            break;
    }
}

int main() {
    srand(time(nullptr));
    pthread_t generator_t;
    init();
    pthread_create(&generator_t, nullptr, generator, nullptr);
    scheduler();
    printf("The average of total wating time is: %lf\n", totalWaitTime / PROCESS_NUM);
    pthread_join(generator_t, nullptr);
    sem_destroy(&sem_scheduler);
    for (auto rq : rqueue)
        for (auto it : rq.list)
            delete it;
    return 0;
}